package sorting;

import java.util.Arrays;

//https://leetcode.cn/leetbook/read/illustration-of-algorithm/p5l0js/
public class 归并排序 {

    private static  void mergeSort(int[] nums,int l,int r){
        if(l >= r) return;
        int m = (l + r) / 2;
        mergeSort(nums, l, m);
        mergeSort(nums, m+1, r);
        int[] tmp = new int[r - l + 1];  // 暂存需合并区间元素
        for(int k=l; k <= r; k++){
            tmp[k-l] = nums[k];
        }
        int i=0,j=m-l+1;   // 两指针分别指向左/右子数组的首个元素
        for(int k=l; k<=r; k++){ // 遍历合并左/右子数组
            if(i == m-l+1)  //i已经移动到右子树组首元素位置，表示左子数组已经都放到nums上了，右子树组不再需要比较，直接放上去就行
                nums[k] = tmp[j++];
            else if(j == r-l+1 || tmp[i] <= tmp[j])//右子数组遍历完 || 左子数组 <= 右子数组（都没遍历完）
                nums[k] = tmp[i++];
            else // 两个子数组都没遍历完 && 左子数组 > 右子数组
                nums[k] = tmp[j++];
        }
        System.out.println("Sorted array: " + Arrays.toString(nums));
    }
    // 调用
    public static void main(String[] args) {
        int[] nums = { 3, 4, 1, 5, 2, 1 };
        mergeSort(nums, 0, nums.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(nums));
    }

}
